class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度
        int n = nums.size(), ret = 1;
        vector<int> dp(n, 1);
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            ret = max(dp[i], ret);
        }
        return ret;
    }
};